package com.topcoder.tcos403;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashSet;
import java.util.StringTokenizer;

public class RookAttack {
	private HashSet<Integer>[] 	avail;
	private int[]				rowMatch;
	private int[]				colMatch;
	private boolean[] 			visited;
	
	public int howMany(int rows, int cols, String[] cutouts) {
		avail = new HashSet[rows];
		rowMatch = new int[rows];
		colMatch = new int[cols];
		visited = new boolean[cols];
		
		for (int i=0; i<rows; i++) {
			avail[i] = new HashSet<Integer>();
			for (int j=0; j<cols; j++) {
				avail[i].add(j);
			}
		}
		
		for (int i=0; i<rows; i++) rowMatch[i] = -1;
		for (int j=0; j<cols; j++) colMatch[j] = -1;
		
		for (String cut : cutouts) {
			StringTokenizer st = new StringTokenizer(cut, " ,");
			while (st.hasMoreElements()) {
				int x = Integer.parseInt((String)st.nextElement());
				int y = Integer.parseInt((String)st.nextElement());
				avail[x].remove(new Integer(y));
			}
		}
		
		int res = 0;
		for (int i=0; i<rows; i++) {
			for (int j=0; j<cols; j++) visited[j] = false;
			res += bfs(i);
		}
		
		return res;
	}
	
	private int bfs(int source) {
		int[] from = new int[rowMatch.length];
		for (int i=0; i<rowMatch.length; i++) from[i] = -1;
		from[source] = source;
		
		ArrayDeque<Integer> dq = new ArrayDeque<Integer>();
		dq.add(source);
		
		while (!dq.isEmpty()) {
			int row = dq.remove();
			for (int col : avail[row]) {
				int next = colMatch[col];
				if (next == -1) {		// find path
					while (from[row] != row) {
						int aux = rowMatch[row];
						rowMatch[row] = col;
						colMatch[col] = row;
						row = from[row];
						col = aux;
					}
					rowMatch[row] = col;
					colMatch[col] = row;
					return 1;
				}
				if (from[next] == -1) {	// hasn't been visited
					dq.add(next);
					from[next] = row;
				}
			}
		}
		
		return 0;
	}
	
	private int dfs(int row) {
		if (row == -1) return 1;
		for (int col : avail[row]) {
			if (!visited[col]) {
				visited[col] = true;
				if (dfs(colMatch[col]) > 0) {
					colMatch[col] = row;
					return 1;
				}
			}
		}
		return 0;
	}
}
